{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find a Good Subset of the Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: goodSubsetofBinaryMatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到矩阵中的好子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始大小为&nbsp;<code>m x n</code>&nbsp;的二进制矩阵&nbsp;<code>grid</code>&nbsp;。</p>\n",
    "\n",
    "<p>从原矩阵中选出若干行构成一个行的 <strong>非空&nbsp;</strong>子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 <strong>好子集</strong>。</p>\n",
    "\n",
    "<p>更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为&nbsp;<code>floor(k / 2)</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回一个整数数组，它包含好子集的行下标，请你将子集中的元素&nbsp;<b>升序</b>&nbsp;返回。</p>\n",
    "\n",
    "<p>如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。</p>\n",
    "\n",
    "<p>一个矩阵 <code>grid</code>&nbsp;的行 <strong>子集</strong> ，是删除 <code>grid</code>&nbsp;中某些（也可能不删除）行后，剩余行构成的元素集合。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]\n",
    "<b>输出：</b>[0,1]\n",
    "<b>解释：</b>我们可以选择第 0 和第 1 行构成一个好子集。\n",
    "选出来的子集大小为 2 。\n",
    "- 第 0&nbsp;列的和为 0 + 0 = 0 ，小于等于子集大小的一半。\n",
    "- 第 1&nbsp;列的和为 1 + 0 = 1 ，小于等于子集大小的一半。\n",
    "- 第 2&nbsp;列的和为 1 + 0 = 1 ，小于等于子集大小的一半。\n",
    "- 第 3&nbsp;列的和为 0 + 1 = 1 ，小于等于子集大小的一半。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[0]]\n",
    "<b>输出：</b>[0]\n",
    "<strong>解释：</strong>我们可以选择第 0 行构成一个好子集。\n",
    "选出来的子集大小为 1 。\n",
    "- 第 0 列的和为 0 ，小于等于子集大小的一半。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1,1,1],[1,1,1]]\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>没有办法得到一个好子集。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 5</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;要么是&nbsp;<code>0</code>&nbsp;，要么是&nbsp;<code>1</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-a-good-subset-of-the-matrix](https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-a-good-subset-of-the-matrix](https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1,0],[0,0,0,1],[1,1,1,1]]', '[[0]]', '[[1,1,1],[1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        dic={}\n",
    "        for idx,row in enumerate(grid):\n",
    "            mask=0\n",
    "            for i,v in enumerate(row):\n",
    "                if v==1:\n",
    "                    mask|=1<<i\n",
    "            for u in dic:\n",
    "                if u&mask==0:\n",
    "                    return [dic[u],idx]\n",
    "            dic[mask]=idx\n",
    "        if len(grid)==1 and 0 in dic:return [dic[0]]\n",
    "        return []\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "\n",
    "        n = len(grid[0])\n",
    "        table = {}\n",
    "        for r in range(len(grid)): #预处理每行的位掩码\n",
    "            table[sum(grid[r][c]<<c for c in range(n))]=r\n",
    "        if 0 in table: return [table[0]] # 存在1行全0，答案就是这一行，不加这个会导致m=1且全0时爆WA\n",
    "        for ke1 in table: \n",
    "            for ke2 in table: \n",
    "                if ke1&ke2==0: return sorted([table[ke1],table[ke2]])\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted((i, j))\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        g = dict()\n",
    "        for i in range(m):\n",
    "            k = 0\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    k |= 1 << j\n",
    "            if k == 0:\n",
    "                return [i]\n",
    "            g[k] = i\n",
    "        for first, a1 in g.items():\n",
    "            for second, a2 in g.items():\n",
    "                for k in range(n):\n",
    "                    if first & 1 << k and second & 1 << k:\n",
    "                        break\n",
    "                else:\n",
    "                    return sorted([a1, a2])\n",
    "                    \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        mask = 2 ** n - 1\n",
    "        cnts = defaultdict(int)\n",
    "        for i in range(m):\n",
    "            num = 0\n",
    "            for j , x in enumerate(grid[i]):\n",
    "                if x == 1:\n",
    "                    num |= (1 << j)\n",
    "            if num == 0:return [i]\n",
    "            nxt = num ^ mask\n",
    "            for state in range(mask):\n",
    "                if (nxt & state) in cnts:\n",
    "                    return [cnts[nxt&state],i]\n",
    "            cnts[num] = i\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        biset = [None] * 32\n",
    "        for j, r in enumerate(grid):\n",
    "            v = sum((d << i) for i, d in enumerate(r))\n",
    "            if v == 0:\n",
    "                return [j]\n",
    "            biset[v] = j\n",
    "        for u in range(32):\n",
    "            if biset[u] is not None:\n",
    "                for v in range(32):\n",
    "                    if biset[v] is not None and (u & v) == 0:\n",
    "                        return sorted([biset[u], biset[v]])\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dic = {}\n",
    "        for i in range(m):\n",
    "            if sum(grid[i]) == 0:\n",
    "                return [i]\n",
    "            t = 0\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    t |= 1 << j\n",
    "            for k, v in dic.items():\n",
    "                if k & t == 0:\n",
    "                    return [v, i]\n",
    "            \n",
    "            dic[t] = i\n",
    "\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            r = 0\n",
    "            for j, _ in enumerate(row):\n",
    "                r+=(_<<j)\n",
    "            if d.get(r) is None: d[r] = i\n",
    "        \n",
    "        if d.get(0) is not None: return [d[0]]\n",
    "        for a, i in d.items():\n",
    "            for b, j in d.items():\n",
    "                if a&b==0: return sorted([i,j])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted((i, j))\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, g: List[List[int]]) -> List[int]:\n",
    "        m = len(g)\n",
    "        n = len(g[0])\n",
    "        s = {}\n",
    "        for j in range(m):\n",
    "            if sum(g[j]) == 0:\n",
    "                return [j]\n",
    "            t = int(''.join([str(k) for k in g[j]]), base=2) \n",
    "            for i in s:\n",
    "                if (i&t)==0:\n",
    "                    return [s[i], j] \n",
    "            s[t] = j \n",
    "        return []\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j,x in enumerate(row):\n",
    "                mask |= x<<j\n",
    "            idx[mask]=i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]    \n",
    "        \n",
    "        for x, i in idx.items():\n",
    "            for y,j in idx.items():\n",
    "                if x &y == 0:\n",
    "                    return sorted((i,j))\n",
    "        return []\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        d = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            r = 0\n",
    "            for j, _ in enumerate(row):\n",
    "                r+=(_<<j)\n",
    "            if d.get(r) is None: d[r] = i\n",
    "        \n",
    "        if d.get(0) is not None: return [d[0]]\n",
    "        for a, i in d.items():\n",
    "            for b, j in d.items():\n",
    "                if a&b==0: return sorted([i,j])\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted((i, j))\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx={}\n",
    "        for i,row in enumerate(grid):\n",
    "            mask=0\n",
    "            for j,x in enumerate(row):\n",
    "                mask|=x<<j\n",
    "            idx[mask]=i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x,i in idx.items():\n",
    "            for y,j in idx.items():\n",
    "                if (x&y)==0:\n",
    "                    return sorted((i,j))\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted((i, j))\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/solutions/2304610/zhi-shang-ju-de-ti-jie-zheng-que-xing-zh-1wju/\n",
    "\n",
    "        \"\"\"\n",
    "        首先要注意到1 <= n <= 5这个数据量，划重点，后面会用到。\n",
    "        为了解释方便，我们称子集大小的一半为“标准”。\n",
    "\n",
    "        1. 首先讨论行子集只有1行时，此情况很简单，因为“标准”为0，所以必须有一行所有元素均为0，否则我们必须考虑选择更多的行来增大“标准”。\n",
    "\n",
    "        2. 当子集行数为2时，“标准”为1，所以要找到两行按列相加后所有元素都小于等于1的行，也就是说必须有两行进行“&”运算后结果为0。\n",
    "        如果找不出这样的两行，我们依然要考虑增加行数来增大“标准”。\n",
    "\n",
    "        3. 当子集行数为3时，其“标准”依然为1，但却要多出一行，完全不用考虑。\n",
    "        不考虑是指，能找到子集为3，为啥不在子集为2的场景时就退出寻找？都是标准为1。多加一行，只会增加列和\n",
    "        不仅行数为3时，所有行数为奇数时都会出现此情况，所以我们只需要考虑行数为偶数的子集。\n",
    "\n",
    "        4. 当子集行数为4时，其“标准”为2，要注意到我们之所以会考虑到将子集取四行，是因为当子集行数为2时，无法找出两行进行“&”运算后结果为0的行，\n",
    "        也就是说，将任意两行按列相加，都至少会出现一个2，那么子集行数为4时，能找出多少个2？\n",
    "        根据组合数的知识，在4行中选2行有6种选法，所以至少会出现6个2，但是1 <= n <= 5，所以必然会有一列之和大于2，\n",
    "        所以当子集行数为2时不行，那么子集行数为4时依然不行。不仅子集行数为4不行，接下来所有更大的偶数都不行,证明方法同理。\n",
    "\n",
    "        所以可以得到结论，如果子集取1行2行都不行，那么就不存在满足条件的取法，所以我们只需要考虑是否有一行元素全部为0，\n",
    "        或者可以找出两行进行“&”运算后结果为0。\n",
    "\n",
    "        \"\"\"\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "\n",
    "        # 有一行都是0，满足子集行数为1，”标准“为0的场景\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "\n",
    "        # 两两之间加起来不大于1，满足子集行数2，”标准“为1的场景\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted([i, j])\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dic = {}\n",
    "        for i in range(m):\n",
    "            mask = 0\n",
    "            for j in range(n):\n",
    "                mask |= grid[i][j] << j\n",
    "            dic[mask] = i\n",
    "        if 0 in dic:\n",
    "            return [dic[0]]\n",
    "        for m1 in dic:\n",
    "            for m2 in dic:\n",
    "                if m1 & m2 == 0:\n",
    "                    return [min(dic[m1], dic[m2]), max(dic[m1], dic[m2])]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        n = len(grid[0])\n",
    "        table = defaultdict(int)\n",
    "        for r in range(len(grid)): #预处理每行的位掩码\n",
    "            temp=sum(grid[r][c]<<c for c in range(n))\n",
    "            if temp==0:\n",
    "                return [r]\n",
    "            table[temp]=r\n",
    "        \n",
    "        for ke1 in table: \n",
    "            for ke2 in table: \n",
    "                if ke1&ke2==0: return sorted([table[ke1],table[ke2]])\n",
    "        return []       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted((i, j))\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted((i, j))\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted((i, j))\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dic = {}\n",
    "        for i in range(m):\n",
    "            mask = 0\n",
    "            for j in range(n):\n",
    "                mask |= grid[i][j] << j\n",
    "            dic[mask] = i\n",
    "        if 0 in dic:\n",
    "            return [dic[0]]\n",
    "        for m1 in dic:\n",
    "            for m2 in dic:\n",
    "                if m1 & m2 == 0:\n",
    "                    return [min(dic[m1], dic[m2]), max(dic[m1], dic[m2])]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "        book = defaultdict(lambda: inf)\n",
    "        for i, v in enumerate(int(\"\".join(map(str, x)), 2) for x in grid):\n",
    "            book[v] = min(book[v], i)\n",
    "        if 0 in book: return [book[0]]\n",
    "        ans = [sorted([book[a], book[b]]) for a, b in combinations(book, 2) if not a & b]\n",
    "        return min(ans) if ans else []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
